首页 > 试题广场 >

链表中倒数最后k个结点

[编程题]链表中倒数最后k个结点
  • 热度指数：358445 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
输入一个长度为 n 的链表，设链表中的元素的值为 ai ，返回该链表中倒数第k个节点。
如果该链表长度小于k，请返回一个长度为 0 的链表。


数据范围：，，
要求：空间复杂度 ，时间复杂度
进阶：空间复杂度 ，时间复杂度

例如输入{1,2,3,4,5},2时，对应的链表结构如下图所示：
其中蓝色部分为该链表的最后2个结点，所以返回倒数第2个结点（也即结点值为4的结点）即可，系统会打印后面所有的节点来比较。
示例1

输入

{1,2,3,4,5},2

输出

{4,5}

说明

返回倒数第2个节点4，系统会打印后面所有的节点来比较。
示例2

输入

{2},8

输出

{}

说明：本题目包含复杂数据结构ListNode，点此查看相关信息
算法知识视频讲解
添加回答
Python 3
L_Mono头像 L_Mono

双指针

class Solution:
    def FindKthToTail(self , pHead: ListNode, k: int) -> ListNode:
        # write code here
        fast = pHead
        slow = pHead
        i = 1
        while i <= k:
            if fast != None:
                fast = fast.next
                i += 1
            else:
                return None
        while fast:
            fast = fast.next
            slow = slow.next
        return slow

栈

class Solution:
    def FindKthToTail(self , pHead: ListNode, k: int) -> ListNode:
        # write code here
        stack = []
        p = pHead
        while p:
            stack.append(p)
            p = p.next
        if len(stack) < k:
            return None
        i = 1
        tmp = None
        while i <= k:
            tmp = stack.pop(-1)
            i += 1
        return tmp
发表于 2022-08-24 15:27:02 回复(0)
Python 3
蓝鲸与风头像 蓝鲸与风 
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param pHead ListNode类 
# @param k int整型 
# @return ListNode类
#
class Solution:
    def FindKthToTail(self , pHead: ListNode, k: int) -> ListNode:
        # write code here
        if not pHead:
            return None
        fast=pHead
        slow=pHead
        for i in range(1,k+1):
            if fast is None:#fast=nullptr
                return None
            fast=fast.next
        while(fast):
            slow=slow.next
            fast=fast.next
        return slow

发表于 2022-08-18 15:10:24 回复(0)
Python 3
杨枝甘露yyds头像 杨枝甘露yyds 
class Solution:
    def FindKthToTail(self , pHead: ListNode, k: int) -> ListNode:
        # write code here
        if not pHead: return None
        if not k: return None
        res = []
        while pHead:
            res.append(pHead.val)
            pHead = pHead.next
        if len(res)<k:
            return None
        
        x = res[len(res)-k:]
        headnew = ListNode(x[0])
        root = headnew
        for i in range(1,len(x)):
            tmp = ListNode(x[i])
            root.next = tmp
            root = tmp
        return headnew
发表于 2022-07-26 00:34:34 回复(0)
Python 3
来个offer叭！头像 来个offer叭！ 
class Solution:
    def FindKthToTail(self , pHead: ListNode, k: int) -> ListNode:
        # 构造一个ahead
        ahead = ListNode(0)
        ahead.next = pHead
        # 慢指针
        p = ahead
        # 快指针
        k1  = pHead
        for i in range(k):
            if k1:
                k1 = k1.next
            else:
                return k1
        if not k1:
            return pHead
        while k1:
            k1 = k1.next
            p = p.next
        return p.next

发表于 2022-07-19 12:07:31 回复(0)
Python 3
风软一江山头像 风软一江山 
class Solution:
    def FindKthToTail(self , pHead: ListNode, k: int) -> ListNode:
        curr = pHead
        try:
            for i in range(k):
                pHead = pHead.next
            while pHead:
                pHead = pHead.next
                curr = curr.next
            return curr
        except AttributeError:
            return None

发表于 2022-07-17 23:03:36 回复(0)
Python 3
Vivimore头像 Vivimore 
class Solution:
    # 快指针先走k步
    # 时间复杂度：O(n)  空间复杂度：O(1)
    def FindKthToTail(self , pHead: ListNode, k: int) -> ListNode:
        fast, slow = pHead, pHead
        for i in range(k):
            if fast:
                fast = fast.next
            else: return None
        while fast:
            fast = fast.next
            slow = slow.next
        return slow
发表于 2022-05-15 11:50:48 回复(0)
Python 3
燕北茶头像 燕北茶 
class Solution:
    def FindKthToTail(self , pHead: ListNode, k: int) -> ListNode:
        # write code here #思路 -反转链表
        if not pHead:
            return
        cur = pHead
        pre = None
        mid = None
        
        num = 1
        l = 1
        while cur:    
            mid = cur           
            cur = cur.next
            mid.next = pre
            pre = mid            
            l+=1
        if k >= l :
            return
        while k >= num :
            mid = pre           
            pre = pre.next
            mid.next = cur
            cur = mid
            num +=1
        return cur
2022/4/11 第一次做，思路：反转链表

发表于 2022-04-11 08:22:04 回复(0)
Python 3
牛客828877215号头像 牛客828877215号
先计算出链表长度，然后减去k
class Solution:
    def FindKthToTail(self , pHead: ListNode, k: int) -> ListNode:
        n=0
        cur=pHead
        while cur:
            n=n+1
            cur=cur.next
        if n<k:
            return None
        for i in range(n-k):
            pHead=pHead.next
        return pHead
发表于 2022-04-02 20:33:03 回复(0)
Python 3
想起来就做两道（JihongRen）头像 想起来就做两道（JihongRen） 
class Solution:
    def FindKthToTail(self , pHead: ListNode, k: int) -> ListNode:
        slow = fast = pHead
        for _ in range(k):
            if fast is None:
                return None
            fast = fast.next
        
        while fast is not None:
            slow = slow.next
            fast = fast.next
        
        return slow

发表于 2022-03-09 20:32:39 回复(0)
Python 3
月上重耳头像 月上重耳 
class Solution:
    def FindKthToTail(self , pHead: ListNode, k: int) -> ListNode:
        len = 0
        p = pHead
        while pHead:
            len += 1
            pHead = pHead.next
        if len < k:
            return
        for i in range(len-k):
            p = p.next
        return p
            

发表于 2022-03-02 20:07:11 回复(0)
Python 3
牛客318213606号头像 牛客318213606号 
class Solution:
    def FindKthToTail(self , pHead: ListNode, k: int) -> ListNode:
        # write code here
        if not pHead:
            return None
        dummyHead=ListNode(-1)
        dummyHead.next=pHead
        l,r=dummyHead,dummyHead
        for i in range(k):
            r=r.next
        if not r:
            return None
        while r.next:
            l=l.next
            r=r.next
        # 此时r 是尾部结点，l是待删除结点的前驱
        return l.next

发表于 2022-02-23 14:32:50 回复(0)
Python 3
Joy_9头像 Joy_9 
class Solution:
    def FindKthToTail(self , head: ListNode, k: int) -> ListNode:
        # write code here
        if not head:
            return head
        fast=head
        low=head
        i=0
        while i<k-1 and fast:
            if fast.next:
                fast=fast.next
                i+=1
            else:
                break
        if i<k-1&nbs***bsp;k==0:
            return None
        while fast.next:
            fast=fast.next
            low=low.next
        return low

发表于 2022-01-05 13:23:44 回复(0)
Python 3
tangjunjun头像 tangjunjun 
class Solution:
    def FindKthToTail(self , pHead: ListNode, k: int) -> ListNode:
        # write code here
        lst=[]
        p=pHead
        N=0
        while p:
            lst.append(p)
            p=p.next
            N+=1
        if k>N&nbs***bsp;k==0: # 考虑k>N或者k=0情况
            return None
        else:
            return lst[-k]

发表于 2021-11-22 23:50:39 回复(0)
Python 3
牛客423617982号头像 牛客423617982号 
class Solution:
    def FindKthToTail(self , pHead , k ):
        # write code here
        cur = pHead
        cur1 = pHead
        i=0
        n=0
        while cur != None:
            cur = cur.next
            i += 1
        if i < k:
            return None
        else:
            while n < i-k:
                cur1=cur1.next
                n += 1
            return cur1

发表于 2021-10-29 11:26:37 回复(0)
Python 3
牛客117124633号头像 牛客117124633号 
class Solution:
    def FindKthToTail(self , pHead , k ):
        # write code here
        fast_pointer = pHead
        slow_pointer = pHead
        length = 0
        while fast_pointer != None:
            fast_pointer = fast_pointer.next
            length += 1
            if length > k:
                slow_pointer = slow_pointer.next
        if k > length:
            return None
        return slow_pointer
快慢指针，欢迎批评指正😃
发表于 2021-09-07 19:55:27 回复(0)
Python 3
buggerNO.1头像 buggerNO.1
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def FindKthToTail(self , pHead , k ):
        # write code here
        if pHead is None or k<=0:
            return None
        #定义一个快指针和慢指针  
        fst = slw = pHead
        t = 0
        #快指针和慢指针间隔k-2个节点
        while t<k-1:
            fst = fst.next
            t+=1
        #当快指针溢出时，表明k大于链表长度，返回None
        if fst is None:
            return None
        #快慢指针同时向后移动，当快指针移动到最后一个节点停止，此时慢指针对应的节点就是倒数第K个节点
        while fst.next != None:
            fst = fst.next
            slw = slw.next
        return slw
发表于 2021-09-04 21:46:48 回复(0)
Python 3
三水123头像 三水123
快慢指针，快的先走k个，然后一起走。就可以找到。 
class Solution:
    def FindKthToTail(self , pHead , k ):
        # write code here
        low = fast = pHead  
        count = 1
        while count<=k:
            fast = fast.next
            count+=1
        while fast is not None:
            fast = fast.next
            low = low.next
        return low

发表于 2021-08-13 13:32:35 回复(0)
提交观点

问题信息

链表
上传者：灵溪吴彦祖
难度：
25条回答 5800浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号